package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/pseudo-palindromic-paths-in-a-binary-tree/description
 *
 * 题型：二叉树的前序遍历，哈希法
 *
 * ```
 * 1457. 二叉树中的伪回文路径
 * 给你一棵二叉树，每个节点的值为 1 到 9 。我们称二叉树中的一条路径是 「伪回文」的，当它满足：路径经过的所有节点值的排列中，存在一个回文序列。
 * 请你返回从根到叶子节点的所有路径中 伪回文 路径的数目。
 *
 * 示例 1：
 * 输入：root = [2,3,1,3,1,null,1]
 * 输出：2
 * 解释：上图为给定的二叉树。总共有 3 条从根到叶子的路径：红色路径 [2,3,3] ，绿色路径 [2,1,1] 和路径 [2,3,1] 。
 *      在这些路径中，只有红色和绿色的路径是伪回文路径，因为红色路径 [2,3,3] 存在回文排列 [3,2,3] ，绿色路径 [2,1,1] 存在回文排列 [1,2,1] 。
 *
 * 示例 2：
 * 输入：root = [2,1,1,1,3,null,null,null,null,null,1]
 * 输出：1
 * 解释：上图为给定二叉树。总共有 3 条从根到叶子的路径：绿色路径 [2,1,1] ，路径 [2,1,3,1] 和路径 [2,1] 。
 *      这些路径中只有绿色路径是伪回文路径，因为 [2,1,1] 存在回文排列 [1,2,1] 。
 *
 * 示例 3：
 * 输入：root = [9]
 * 输出：1
 *
 *
 * 提示：
 * 给定二叉树的节点数目在范围 [1, 105] 内
 * 1 <= Node.val <= 9
 * ```
 */
class leetcode_1457 {
    @Test
    fun test_3() {
        val root = TreeNode(9)
        val actual = pseudoPalindromicPaths(root)
        val expected = 1
        Assert.assertEquals(expected, actual)
    }

    private fun pseudoPalindromicPaths(root: TreeNode?): Int {
        /**
        题型：二叉树的前序遍历，哈希法

        思路：
        1 收集路径的每个节点
        2 当节点为叶子节点时，判断是否该路径是否是回文，若是则，count + 1
        判断回文：奇数的个数<= 1

        空间复杂度：O（N）
        时间复杂度：：O（N）
         */
        val path: IntArray = IntArray(10)
        root?.let {
            path[it.`val`] = 1
        }
        return collect(root, path)
    }

    fun collect(root: TreeNode?, path: IntArray): Int {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return 0
        }
        // 3 确定单次递归的处理逻辑：前序遍历
        // 中
        var count: Int = 0
        if (root.left == null && root.right == null) {
            if (isValid(path)) {
                count = 1
            }
        }
        // 左
        var isLeftCount: Int = 0
        root.left?.let {
            path[it.`val`] = path[it.`val`] + 1
            isLeftCount = collect(it, path)
            path[it.`val`] = path[it.`val`] - 1
        }

        // 右
        var isRightCount: Int = 0
        root.right?.let {
            path[it.`val`] = path[it.`val`] + 1
            isRightCount = collect(it, path)
            path[it.`val`] = path[it.`val`] - 1
        }

        return count + isLeftCount + isRightCount
    }

    private fun isValid(paths: IntArray): Boolean {
        // 判断是否是回文？出现奇数次数的元素个数，若 1 或 0，则是回文，若 >= 2，则不是回文。
        var count: Int = 0
        for (i in 1 until paths.size) {
            if ((paths[i] % 2) != 0) {
                count = count + 1
                if (count >= 2) {
                    // println("isValid:hash - ${paths.contentToString()}, return false")
                    return false
                }
            }
        }

        // println("isValid:hash - ${paths.contentToString()}, return true")
        return true
    }


    fun pseudoPalindromicPaths2(root: TreeNode?): Int {
        // 超时
        val path: ArrayList<Int> = ArrayList()
        root?.let {
            path.add(it.`val`)
        }
        return collect(root, path)
    }

    fun collect(root: TreeNode?, path: ArrayList<Int>): Int {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return 0
        }
        // 3 确定单次递归的处理逻辑：前序遍历
        // 中
        var count: Int = 0
        if (root.left == null && root.right == null) {
            if (isValid(path)) {
                count = 1
            }
        }
        // 左
        var isLeftCount: Int = 0
        root.left?.let {
            path.add(it.`val`)
            isLeftCount = collect(it, path)
            path.removeAt(path.size - 1)
        }

        // 右
        var isRightCount: Int = 0
        root.right?.let {
            path.add(it.`val`)
            isRightCount = collect(it, path)
            path.removeAt(path.size - 1)
        }

        return count + isLeftCount + isRightCount
    }

    fun isValid(path: ArrayList<Int>): Boolean {
        if (path.isEmpty()) {
            return false
        }


        // value,count
        val map: HashMap<Int, Int> = HashMap()
        for (item in path) {
            map[item] = (map[item] ?: 0) + 1
        }
        // println("$path:$map")
        var count: Int = 0
        for (entry in map.entries) {
            if (entry.value % 2 != 0) {
                count++
            }
        }
        return count <= 1
    }
}